// https://leetcode.cn/problems/lemonade-change/

// 题干：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
//      每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。
//      你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
//      注意，一开始你手头没有任何零钱。给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。
//      如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

// 示例：输入：bills = [5,5,5,10,20]
//      输出：true

// 碎语：// 贪心算法的策略
// 解决问题的策略，局部最优 -> 全局最优
// 1.把解决问题的过程分成若干步
// 2.解决每一步的时候，都选择当前看起来最优的解法
// 3.“希望”得到全局最优解

// 贪心算法的两个特点：
// 1.贪心策略的提出：没有具体的标准以及模板的
// 2.可能每一道题的贪心策略是不同的

// 贪心策略的正确性
// 因为有可能“贪心策略”是一个错误的方法
// 正确的贪心策略，我们是需要证明的

// 常用的证明方法：数学中见过的所有证明方法

// 1.找零问题的证明：
// 20 10 5 1的张数为A B C D
// 分析可得B >= 2 C >= 2 D >= 5这种情况不可能实现
// B <= 1, C <= 1，D <= 4 是合法限定范围
// 假设贪心解出来的答案 [a,b,c,d],最优解[A,B,C,D]
// a >= A,若a>A，发现后面凑不出来20快钱，于是错误，得到a=A
// 剩下凑的钱一样，同理b=B，c=C，最后d=D

// 学习方向：遇到不会的贪心题，很正常，把心态放平
// 前期学习的时候，把重点放在贪心的策略上，然后把这个策略当作经验吸收
//
// 当知道贪心的正确后，要想着如何去证明，因人而异

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool lemonadeChange(vector<int>& bills)
    {
        int n = bills.size();
        int balance[2] = {0}; // bills[0]存5，bills[1]存10，bills[2]存20

        for (int i = 0 ; i < n ; i++){
            // 当客户给5元
            if (bills[i] == 5) balance[0]++;

            // 当客户给10元
            if (bills[i] == 10){
                if (!balance[0]) return false;
                balance[0]--;
                balance[1]++;
            }

            // 当客户给20元
            // 此时应尽量选择找零10+5的方案
            if (bills[i] == 20){
                if ((!balance[0] || !balance[1]) && balance[0] < 3) return false;

                // 先采取第一种10+5方案
                if (balance[0] >= 1 && balance[1] >= 1) balance[0]--,balance[1]--;
                // 若无法满足，采取第二种5+5+5方案
                else balance[0] -= 3;
            }
        }

        return true;
    }
};

int main()
{
    Solution sol;
    vector<int> bills = {5,5,5,10,20};

    cout << sol.lemonadeChange(bills) << endl;

    return 0;
}